package com.sourcetrip.algorithm.bf;

import com.sourcetrip.algorithm.inter.BloomFilter;

/**
 * @author: ZhouBert
 * @date: 2021/1/20
 * @description: 可定制的布隆过滤器 真实的业务场景：
 * 已知误判率 p, 数据规模 n ，定制 hash 函数为 k 的具有 m 个二进制长度的 bf.
 * --
 * bf 的删除：
 * 使用引用计数的方法：将 arrays 用 int[] 来替代 byte[] ，每次 hash 落地的索引，就+1，删除就-1；
 * 但是这样牺牲了空间，一般不用删除。
 * --
 * 案例分析：
 * 用 hash 表存 1_0000_0000 个 email 地址 VS bf 存 一个亿 的 email 地址：
 * 前者-一个 email 的内存地址 = 1个字节 = 8 bit ;假设hash 存储效率为 50%，那么
 * 结果= 1_0000_0000 * 8 / 0.5 bit =  1.6GB
 * 后者-
 */
public class CustomedBloomFilter<E> implements BloomFilter<E> {

	/**
	 * 二进制（bit）向量的长度
	 */
	int bitSize = 0;

	/**
	 * 为什么用 long[] 而不是用 int[] 之类的呢？
	 * 感觉都可以
	 */
	long[] bits;

	/**
	 * hash 的计算个数
	 */
	int hashSize = 0;

	int LONG_REMAINDER = Long.SIZE - 1;

	/**
	 * 根据已知的 数据规模和 误判率构造出对应的 bf
	 *
	 * @param n 数据规模
	 * @param p 误判率, 取值范围(0, 1)
	 */
	public CustomedBloomFilter(int n, double p) {
		if (n <= 0 || p <= 0 || p >= 1) {
			throw new IllegalArgumentException("wrong n or p");
		}

		double ln2 = Math.log(2);
		//按照公式计算出 m 和 k
		// 求出二进制向量的长度
		bitSize = (int) (-(n * Math.log(p)) / (ln2 * ln2));
		// 求出哈希函数的个数
		hashSize = (int) (bitSize * ln2 / n);
		// bits数组的长度
		bits = new long[(bitSize + Long.SIZE - 1) / Long.SIZE];
		//TODO:分页的技巧：精髓在于 -1
		// 每一页显示100条数据, pageSize
		// 一共有999999条数据, n
		// 请问有多少页 pageCount = (n + pageSize - 1) / pageSize
	}

	/**
	 *
	 * @param ele
	 * @return	返回了一个 boolean 的好处在于：可以马上知道 添加的元素对于 bf 而言是否为一个新的元素
	 */
	@Override
	public boolean put(E ele) {
		nullCheck(ele);

		//根据 ele 计算两个 整数
		int hash1 = ele.hashCode();
		int hash2 = hash1 >>> 16;

		//只要任意一个索引的地址与旧值发生了变动，那就认为 put 变动了
		boolean result = false;

		for (int i = 1; i <= hashSize; i++) {
			int combinedHash = hash1 + (i * hash2);
			if (combinedHash < 0) {
				//如果是负数 -> 取反
				combinedHash = ~combinedHash;
			}
			// 生成一个二进位的索引
			int index = combinedHash % bitSize;
			// 设置index位置的二进位为1
			if (set(index)) {
				result = true;
			}
		}

		return result;

	}

	/**
	 * 找到 long[] 中的二进制位并设置为 1
	 * long[i] 占据 64 位
	 * --
	 * 得到的 bits 中的索引位置是从左到右的；
	 * 但是 标记为1 的时候是从右到左的。（long 内部是从右到左的）
	 * 这样比较方便，其实关系也不大，保证唯一性即可！
	 *
	 * @param index
	 * @return	true-说明对应bit 索引的位置从 0-> 1 ;false 说明该位置原本就是1
	 */
	private boolean set(int index) {
		// bits 中 的索引位置
		int bitsIndex = index / Long.SIZE;
		// long 内部左移的步长（通过 位运算 & 替代 取余）
		int leftIndex = bitsIndex & LONG_REMAINDER;
		//修改前的 long 值
		long oldValue = bits[bitsIndex];
		//准备进行 & 运算的值
		int bitValue = 1 << leftIndex;
		//设置索引上的值
		bits[bitsIndex] = oldValue | bitValue;
		//证明原来的位置上是 0
		return (oldValue & bitValue) == 0;
	}

	@Override
	public boolean contains(E ele) {
		return false;
	}


	private void nullCheck(E value) {
		if (value == null) {
			throw new IllegalArgumentException("Value must not be null.");
		}
	}
}
